The appendix of seventy-two frames is a program definition document for firmware and software discussed herein. The second and third frames are a table of contents.
This invention relates generally to machines and procedures for incremental printing or copying of text or graphics on printing media such as paper, transparency stock, or other glossy media; and more particularly to a machine and method that constructxe2x80x94under direct computer controlxe2x80x94text or images from individual colorant spots created on a printing medium, in a two-dimensional pixel array. For purposes of this document, by the phrases xe2x80x9cincremental printingxe2x80x9d and xe2x80x9cincremental printerxe2x80x9d I mean to encompass all printers and copiers that perform computer-controlled construction of images by small increments.
The invention advances the art of both printmasks and halftoning or so-called xe2x80x9cditherxe2x80x9d masks. For the sake of simplicity the invention will be described primarily with respect to printmasks, but it is to be understood that in many cases this term equivalently encompasses halftoning or dither masks. Without further elaboration, a person of common skill in the art will readily understand when such equivalency is present and when it is not.
The invention employs printmode and dithering techniques to optimize image quality vs. operating time and data-storage costs, and is particularly but not exclusively beneficial in scanning thermal-inkjet machines and methods. For definiteness the discussion in this document will refer to inkdrops, coalescence and other features and phenomena associated with inkjet printers; however, it is to be understood that equivalent characteristics of other printer types are encompassed within that discussion.
Inkjet printers, and certain other types of incremental printers, are inherently capable of a very limited number of tonal levels. To achieve a moderate range of tonal variations in such printers, halftoning or dither masks are used to transform or xe2x80x9crenderxe2x80x9d input variations in intensity in the form of spatially varying densities.
The eye integrates the spatial variations to, in effect, reconstruct a semblance of continuous-tone capability. The halftoning process, in incremental printers, sometimes employs masks known as dither masks or halftone masks, and the preparation of these masks is a matter of importance in terms of preparation time, data storage, and final output image quality.
To achieve vivid colors in inkjet printing with aqueous inks, and to substantially fill the white space between addressable pixel locations, ample quantities of ink must be deposited. Doing so, however, requires subsequent removal of the water basexe2x80x94by evaporation (and, for some printing media, absorption)xe2x80x94and this drying step can be unduly time consuming.
In addition, if a large amount of ink is put down all at substantially the same time, within each section of an image, related adverse bulk-colorant effects arise. These include so-called xe2x80x9ccoalescencexe2x80x9d and xe2x80x9cbleedxe2x80x9d of one color into another (particularly noticeable at color boundaries that should be sharp), xe2x80x9cblockingxe2x80x9d or offset of colorant in one printed image onto the back of an adjacent sheet with consequent sticking of the two sheets together (or of one sheet to pieces of the apparatus or to slipcovers used to protect the imaged sheet), and xe2x80x9ccocklexe2x80x9d or puckering of the printing medium. Various techniques, discussed below, are known for use together to moderate these adverse drying-time effects and bulk- or gross-colorant effects.
(a) Prior Heat-application Techniques
Among these techniques is heating the inked medium to accelerate evaporation of the water base or carrier. Heating, however, has limitations of its own; and in turn creates other difficulties due to heat-induced deformation of the printing medium.
Glossy stock warps severely in response to heat, and transparencies too can tolerate somewhat less heating than ordinary paper. Accordingly, heating has provided only limited improvement of drying characteristics for these plastic media.
As to paper, the application of heat and ink causes dimensional changes that affect the quality of the image or graphic. Specifically, it has been found preferable to precondition the paper by application of heat before contact of the ink; if preheating is not provided, so-called xe2x80x9cend-of-page handoffxe2x80x9d quality defects occurxe2x80x94this defect takes the form of a straight image-discontinuity band formed across the bottom of each page when the page bottom is released.
Preheating, however, causes loss of moisture content and resultant shrinking of the paper fibers. To maintain the paper dimensions under these circumstances the paper may be held in tension, but this too induces still other types of image defects requiring yet further innovation to overcome them.
(b) Printmode Techniques
Another useful technique is laying down in each pass of the pen only a fraction of the total ink required in each section of the imagexe2x80x94so that any areas left white in each pass are filled in by one or more later passes. This tends to control bleed, blocking and cockle by reducing the amount of liquid that is all on the page at any given time, and also may facilitate shortening of drying time.
The specific partial-inking pattern employed in each pass, and the way in which these different patterns add up to a single fully inked image, is known as a xe2x80x9cprint modexe2x80x9d. Heretofore most efforts in design of print modes have focused upon difficulties introduced by regularity or repetition of patterns previously regarded as inherent in printmode techniques.
For example, some print modes such as square or rectangular checkerboard-like patterns tend to create objectionable moire effects when frequencies or harmonics generated within the patterns are close to the frequencies or harmonics of interacting subsystems. Such interfering frequencies may arise in dithering subsystems sometimes used to help control the paper advance or the pen speed.
More recently, however, attention has turned to use of random or more-properly xe2x80x9crandomizedxe2x80x9d patterns. These are introduced in the coowned patent documents listed earlier and will be discussed in greater detail shortly.
(c) Known Technology of Printmodes: General Introduction
The pattern used in printing each nozzle section is known as the xe2x80x9cprintmode maskxe2x80x9d or xe2x80x9cprintmaskxe2x80x9d. The term xe2x80x9cprintmodexe2x80x9d is more general, usually encompassing a description of a mask, the number of passes required to reach full density and the number of drops per pixel defining xe2x80x9cfull densityxe2x80x9d.
One particularly simple way to divide up a desired amount of ink into more than one pen pass is the checkerboard pattern mentioned above: every other pixel location is printed on one pass, and then the blanks are filled in on the next pass. This pioneering strategy was quickly recognized as inadequate for highly demanding competitive modern printers because of ink coalescence along diagonals, inability to correct moire phenomena, and also the appearance of so-called xe2x80x9cbandingxe2x80x9d or evident boundaries between abutting ink swaths.
To reduce such horizontal banding problems (and sometimes minimize the moire patterns) discussed above, a print mode may be constructed so that the paper advances between each initial-swath scan of the pen and the corresponding fill-swath scan or scans. In fact this can be done in such a way that each pen scan functions in part as an initial-swath scan (for one portion of the printing medium) and in part as a fill-swath scan.
This technique tends to distribute rather than accumulate print-mechanism error that is impossible or expensive to reduce. The result is to minimize the conspicuousness ofxe2x80x94or, in simpler terms, to hidexe2x80x94the error at minimal cost.
All of these strategies are now well known and have been elaborated to a very great extent, including the use of space- and sweep-rotated printmode masks, autorotating printmode masks (in which rotation occurs even though the pen pattern is consistent over the whole pen array and is never changed between passes), and steeply angled, separated mask-pattern lines. An extensive discussion of such methods appears in U.S. Pat. No. 5,677,716 of Cleveland. Analogous problems and solutions are known in regard to dither masks as well.
(d) Nozzle-variation Effects
Different groups or areas of nozzles in a pen have different effects on image quality. Only a few techniques have been introduced for adapting printer control mechanisms to accommodate or even exploit such variations.
European Patent 730,967 of Nicoloff et al. explains that overlap between two different-color inks, during a single scan, can be prevented by operating only a section of each nozzle array (i.e., pen) during such a single scan. It appears that the selection of the section to be operated, in Nicoloff, is consistent.
United Kingdom Patent 2,302,065 of Nobel et al. deals exclusively with text printing. It teaches variation of printhead alignment with respect to the lines of text, from page to page or at other intervalsxe2x80x94so that top and bottom nozzles can be used about equally and also causes wear of middle nozzles to be more uniform.
As pens are fabricated by automatic techniques that continually increase in efficiency and speed, new kinds of nozzle variations continue to appear. Further development in the area of dealing with such variations is therefore needed.
(e) A New Generation of Banding Problems
Heretofore, however, all these many ingenious stratagems have fallen short of eliminating banding. This is particularly true in the midtone range where small repetitive patterns, even subtle patterns, often become very objectionably conspicuous. Such difficulties are known in regard to both dither masks and printmasks.
Particularly as to the latter, the current generation of efforts includes the work outlined in at least the Serra and Chang documents to eliminate such problems by xe2x80x9crandomizingxe2x80x9d of masks, i.e. building masks by pseudorandom processes. Generally speaking, both these groups of workers teach the possibility of operating a randomized mask-building process in real time, in a printerxe2x80x94but reject that possibility, teaching away from it in favor of human inspection of computer-generated candidate masks, for best esthetics of printed results.
Chang suggests a balance between ink-media artifacts (which he associates with such esthetic choice by a live person) and mechanical artifacts (which he associates with randomization as a curative). Chang accordingly teaches that the inspection step is essential at least for the present.
The efforts of both Serra and Chang are distinct and important improvements over the prior art. With respect to their largest objectives, however, these efforts have foundered on the persistence of conspicuous and distinctivexe2x80x94even though substantially randomxe2x80x94patterns that repeat dozens of times across a typical image.
In hindsight, the reason behind such persistence is clear. Operation of printers using these newest, randomized masks amounts to a superposition of a repeating mask pattern with a constant pattern of pen nozzle misdirections, weak or failed nozzles, and other flaws of static character. The system convolves the same mask patterns with the same nozzles over and over.
The resulting granularity is generally far larger than individual pixels or inkdrops. Although some shapes can be reduced for a particular image by tinkering with mask patterns, this approach too is typically prohibitive with common imagesxe2x80x94which are ordinarily very complex.
Of course it is not intended here to unduly criticize the contributions of these skillful and talented workers in this field, who have produced important and useful advances. Yet that effort leaves room for improvement.
Indeed, from the perspective of a skilled person in this field, intuitively it might appear that only a mask on the order of a major fraction of a full-page image would suffice to truly eliminate conspicuous patterning. From that perspective the results of these copending patent documents appear to be perhaps some two orders of magnitude away, in terms of mask size, from such an expectably successful size standard.
Earlier masks have been small. In the printing-medium advance direction (vertical for a portrait-format image), mask height customarily has been equal to the number of nozzles divided by the number of passes, or an even smaller quotient. In the scan-axis direction (horizontal), mask width ordinarily has been equal to the height or lessxe2x80x94typically eight to thirty-two pixels.
These numbers represent very small fractions of a full-page image width at the modern resolution standard of twenty-four pixels per millimeter (six hundred pixels per inch). Even increasing mask size to, say a third or a half of full-page width calls for an increase by a factor of some fifty to seventy.
That is a daunting prospect, since such very large masks require very large memoryxe2x80x94and different masks are required for various conditions, particularly including type of printing medium as well as printing speed. The crosscombinations of these conditions rise quickly to require at least some eight or twelve different masks. The cost of storing not one but numerous manufacturer-supplied multimegabyte-size masks, and the competitive handicap of requiring such mask storage in a computer attached to a printer, are all but prohibitive.
The picture as seen from the current generation of advances is similarly adverse with regard to generation of such large masks in the field. While the Serra results may provide somewhat better image quality, both the Serra and Chang algorithms appear to be too expensive computationally to implement in onboard processing systems of a printer, or even in a printer driver operable in most personal computers.
With such a strategy, a mask-building program might be started on a workstation to operate overnight, and the next day one or two more-or-less valid solutions might be found to test with real conditions. This alone points up a major drawback at a conceptual level: it is analogous to assigning a lower primate to press typewriter keys essentially at randomxe2x80x94with a person necessarily inspecting the results from time to time to see whether what was typed makes sense.
If not, the person discards all of that and the animal starts againxe2x80x94a painfully inefficient procedure. Moreover, notwithstanding commitment to such a computationally intensive method, as already indicated the masks built in this way were rather small, on the order of sixteen by thirty pixels.
Another of the current generation of advances in the printmasking art, the Doron document mentioned earlier, proposes building a good mask automatically at each effort, and suggests that this may be accomplished within a printer in the field and in real time (i.e., when or shortly before the mask is needed). Doron indicates that a differently configured mask is selected for each printing operationxe2x80x94that is, for each printer pass in a repeating series of, say, four or five passesxe2x80x94and his approach evidently thus entails use of not one but several discrete masks for each image.
The printer selects a different one of these masks for each pass, which is to say that different masks are applied to printing of different image portions. In the earlier procedure of building a mask, Doron""s procedure operates in a three-dimensional space that is a vertical stack of pixel grids, each successive grid or plane representing a higher layer of inkdrops applied in succeeding passes, or by later-arriving nozzles in a single pass.
Doron appears to introduce randomness at two stages of his procedures. First, in the mask-building stage he randomly selects a series of vertical columns in the stackxe2x80x94e.g., columns that underlie particular pixel positions in the topmost gridxe2x80x94for processing, one column at a time.
In processing each column he fills-in printing parameters for the several grids in the stack, observing selection rules that refer to columns which have been previously filled in. The selection rules appear to result in an essentially deterministic series of selected xe2x80x9cparameterxe2x80x9d numbers down the column, given the columns filled in previously. The random order of column selections in this way controls the final overall three-dimensional array of parameters.
Second, at run time Doron""s control program randomly selects one of a number of the randomly generated masks for use in each xe2x80x9cprinting operationxe2x80x9d as mentioned above. The degree of randomness in his pseudorandom system appears to be fixed by these two processes.
Although it uses plural masks in conjunction for printing of each image, his system appears to require relatively modest quantities of data storage. It requires more than just the storage for one mask, but less than would be required for permanent storage of all necessary masks, and a small amount in total because each of his masks is rather small.
The efficacy of the system is unclear, in that it attempts to rely upon continuously shifting among several available masks to break up patterning but the individual masks are small. Doron""s mask height (i.e. a y dimension in the pixel grid) is his pen height, preferably one hundred twenty-eight pixels; however, his most-highly preferred mask width is said to be only thirty-two pixels.
Thus if the number of masks is also rather small, some potential for repetitive patterns breaking through may remain. On the other hand if the number of masks is adequately large and the selection truly randomized, then the system may exhibit adverse effects of highly random masking. Since such effects are part of the recognitions driving the present invention, they will be explained further in the following sections.
(f) Conclusion
As shown above and elaborated in the following sections, various obstacles of computing time, data storage, a fixed degree of randomness and repetitive small or narrow (although randomized) mask patterns have continued to impede achievement of uniformly excellent inkjet printingxe2x80x94at high throughputxe2x80x94on all industrially important printing media. Thus important aspects of the technology used in the field of the invention remain amenable to useful refinement.
The present invention introduces such refinement. Before proceeding to a relatively rigorous description or definition, this section offers some informal comments that are for orientation only and should not be taken as defining the invention.
The terms xe2x80x9cprintmaskxe2x80x9d and xe2x80x9cshingling maskxe2x80x9d may be used interchangeably. Dither masks are used for a different purpose, as outlined earlier, and accordingly have distinctly different microstructure. Each of these three terms, however, refers to a two-dimensional array of cells in which each cell contains a given amount of ordered numbers. (Slightly nonidiomatic phrases such as xe2x80x9camount of . . . numbersxe2x80x9d are used in this document in preference to phrases such as xe2x80x9cnumber of numbersxe2x80x9d that are idiomatically more common but confusing.)
In dither masks, each number in the cell represents, most typically, a discriminator number against which essentially a continuous-tone (or high-multilevel) signal is tested to determine whether inking in the corresponding pixel will occur or not. It is a decisional tool relating to spatial distribution of ink spots.
In printmasks, each number in the cell represents a pass in which a dot will be printed. Stepping or xe2x80x9ctilingxe2x80x9d this array in two orthogonal directions over the print medium describes the pass in which the printhead will fire each drop; thus a printmask is a decisional tool relating to temporal distribution of the spots ordained by the halftone or dither process.
The amount of numbers in a printmask cell equals the maximum number of drops that the printer can fire in any given pixel (dots per pixel, or xe2x80x9cdppxe2x80x9d). The order of the numbers in the cell corresponds to the order of passes in which to fire: that is, the first number will be used for the first drop, the second number for the second drop in the same pixel location, and so on.
For a printer that can fire two drops per pixel, for example, the first number in a cell represents the pass number in which the first drop is to be fired; in case of firing a second drop, the second number will be used. A halftoning algorithm, which may operate in the printer or in an associated printer driver in a connected computer, controls the number of drops to fire in a given location.
The ordered set of numbers in each cell can be interpreted as representing a third dimension. A three-dot-per-pixel mask, for example, can be represented by three two-dimensional arrays, each one containing just one number per cell, and representing one level.
If only one drop has to be fired, the number in the lowest level array will be used; if two drops have to be fired, the numbers in the lowest level and the second level arrays will be used. In this document the arrays representing each level will be referred to as layers or planesxe2x80x94not to be confused with the color xe2x80x9cplanesxe2x80x9d often mentioned in connection with multicolor printing.
This approach does not yield a completely general notation for masking. It implies that, if pass number n is being used when one drop has to be fired, passes n and m will be used for firing two drops, and passes number n, m and g for three drops. It could be desirable, though, to use pass n for just one drop, but passes m and g for two drops. The first approach may be called sequential, and will be the only one addressed here.
Designing a printmode determines the strategy that the printer will follow to put drops onto the paper. This strategy has to respect certain restrictions, and tries to accomplish certain goals of print quality and throughput.
The restrictions come from the physics of the pen and ink-media interaction: firing two consecutive drops, for instance, could cause the firing frequency of the pen to be too high, or placing two drops next to each other in the same pass would cause coalescence. Goals often come from marketplace considerations, and for dither masks they may take the form of xe2x80x9ceffective resolution of image detail finer thanxe2x80x9d a specified value; for printmasks they may instead take the form of xe2x80x9cbanding freexe2x80x9d at some specified distance, or xe2x80x9cbetter color gamut thanxe2x80x9d a specified product, or xe2x80x9cimage quality higher thanxe2x80x9d some known reference standard.
This document relates to an invention which in part represents an advance because it focuses on the restrictions, and particularly upon unambiguous ways to define them in symbols. Such notations will be described, and an analysis of the conditions under which it is always possible to create a mask that satisfies the restrictions will be offered.
The invention provides or includes a method for synthesizing masks, given restrictions expressed in such a form and under just such conditions. In contrast to related approaches discussed in an earlier section, the present invention defines a set of constraintsxe2x80x94the grammatics, so to speak, which the unfortunate animal previously mentioned was supposed to respect, but was never taught.
The invention thereby, within the immediate process of building a mask, makes certain that every single element of the mask is going to respect them. This approach assures that every run of the algorithm will provide a valid solution. In comparison with the overnight techniques required to produce possibly usable 16xc3x9730 masks, the present invention operating on the same workstation finds a guaranteed-valid 512xc3x97512 mask in two or three seconds.
Small Masks, Large Masks and the Odds of Finding a Usable Mask
Design of print modes has traditionally been limited to small printmasks, something like sixteen pixels wide by two hundred forth pixels tall. Such a limitation, together with a helpful restriction that divides the nozzles into zones corresponding to the number of passes, makes the problem a tractable one.
It is still difficult, but tractable. A writing-systems engineer can draw zeros and ones in the places where it is desirable for the pen to firexe2x80x94and then can visually inspect the result, make sure the restrictions are respected, and even draw a nice pattern.
This method decides the strategy for putting the drops on the paper, looking at the pen. A printmask is designed to be the size of the nozzle plate, and in effect is something the pen carries with it. This has an important drawback: every defect, every pattern, will always be repeated in every swath the same way, thus having the tendency to produce bands.
This is where large printmasks can come into play. The basic idea is to change the focus from the pen to the plot. It is not necessary to be restricted to something the size of the pen that will be repeating. Instead it is possible to look at the plot and decide to ink one particular pixel in the first pass, another particular pixel in the fourth, and so on. In principle this can be done with any number of pixels, even with the entire image frame.
This approach, however, can no longer be followed with the traditional methods of the writing systems engineer. No amount of skill or patience would enable the engineer to manually find, for example, a 1024xc3x971024 array of numbers that fulfills the required restrictions.
Given a certain number of passes, there is a maximum number of restrictions that will leave degrees of freedom to find the mask. More specifically, if the number of restrictions (expressed in a particular notation discussed later) is lower than the number of passes, it will always be possible to solve the problem with a deterministic algorithm.
If the number of restrictions is equal to or higher than the number of passes, finding a mask becomes a probabilistic exercise that depends on the size of the mask (it is possible to compute the probability). Such a mask is overconstrained and will not be possible to find with a deterministic straightforward algorithm. In general, it will require a number of iterations roughly related to the probability of finding a solution.
If the desired mask is small, even if the restrictions overconstrain the problem, it is relatively easy to find a solution. The odds, however, decrease drastically as the size of the mask increases.
The Tools, and How to Work with Large Masks
The innovations described in this document are associated with development of a computer program that, given a set of restrictions and a definition for the mask (size and number of passes), will try to find a mask that fulfills the restrictions. The phrase xe2x80x9ctry to findxe2x80x9d here means that if the problem is underconstrained, the program will always find the mask on the first attempt; and if the problem is overconstrained it will sometimes find a solution and sometimes not.
This program can be caused to run in printer firmware, or in the processes of an application-specific integrated circuit (ASIC), or as part of a printer driver that in turn is running in a computer attached to a printer. The program can be used in a number of ways:
It can help in the design of small masks. It can be used to find underconstrained masks straightforwardly.
More interestingly, together with a shell script it is also able to find overconstrained masks; or it can be piped to another program and there used to find a mask that has certain special properties. In these last two cases, it becomes a new but much more sophisticated form of the previously discussed analogy to animals typingxe2x80x94but now with no need for human intervention to check quality.
It also can do the design of a large mask, as for instance a printmask that can be tiled with a set of restrictions. Again, if such a mask is underconstrained the program will always produce a solution.
If the large-mask problem is overconstrained, the number of trials needed will depend on the probability of finding a solution (in general, the number of trials may be unacceptably large). In this case the design can take either of two different approaches:
The designer of a mask decides what restrictions are necessary, how many passes and so on, and produces a mask of the desired size. This mask goes to the printer or driver, where it is stored and used.
In this case, the mask can be overconstrained (assuming the designer thinks this is necessary, and has enough computer power and time to find it). An important drawback is that the mask will have to be tiled, and this implies more restrictions.
The designer of the mask decides on the restrictions, number of passes and so on, and the printer uses them to produce the mask on the flyxe2x80x94in other words, in real time, while actually printing an image. This has two great advantages, coming from the fact that the mask doesn""t have to be tiled: there are fewer restrictions, and there are no repeating patterns.
It also has disadvantages: the mask has to be produced straightforwardly, so it cannot be overconstrained. This approach also requires some computing power from the printer, but it appears feasible with some modern printers which answer to that requirement.
Constraints
a constraint for present purposes is defined as any design criterion that a mask is expected to satisfy. Two main types of constraint are currently in use: spatial constraints and (primarily for printmasks) pen-usage constraints. Constraints can be applied within a single plane of a mask, between planes, or between different masks (for example, to make certain that yellow will not print in the same pass as cyan).
(1) Neighborhood Constraints
These are spatial constraints that define restrictions on the placement of dots with respect to a pivotal point (a central point in a constraint diagram as will be seen below), as a function of their relative position or so-called xe2x80x9cdistancexe2x80x9d, or both. In this section, which will be found most natural if interpreted in terms of printmasks, xe2x80x9cdistancexe2x80x9d always means a difference between two pass numbersxe2x80x94so that in effect this xe2x80x9cdistancexe2x80x9d is measured in units of time.
For example, if a position in the mask that has a value of four is at the pivotal point, and the neighbor in the relative position (xe2x88x921,0), the point immediately to the left, has a value of one, then the distance is 4xe2x88x921=3. Note also that since the number of passes is a repeating sequence from one to n, so that the pattern in effect wraps, the distance between n and one is one, not nxe2x88x921.
All the points in the mask should comply with all neighborhood constraints. Neighborhood constraints are always defined as a function of relative positions with respect to a pivotal point: all the points in the mask should be able to function as pivotal points, and satisfy the defined constraints with respect to the defined neighbors. The only exceptions are the boundary cells of the mask; it is often favorable to define different neighborhood constraints for the center of the mask from those of the bordersxe2x80x94the latter being sometimes called xe2x80x9cseam constraintsxe2x80x9d.
A general way to describe neighborhood/spatial constraints is defining, for any given neighbor, a weight for any given distance (distance, again, is here the difference between two pass numbers). The weight goes from zero (meaning forbidden) to one (meaning accepted).
For a particular pivotal point that can be any point in the matrix, constraints specify a set of limitations in terms of pass numbers for the neighbors. For example, this scheme
default 1
(0,1) # the upper neighbor
[0:0.0] # distance 0 (i.e. same plane), weight 0.0
[1:0.0] # distance 1, weight 0.0 (i.e. forbidden)
(xe2x88x921,0) # the left neighbor
[2:0.1] # distance 2, weight 0.1 (xe2x80x9calmost forbiddenxe2x80x9d)
[4:0.1] # distance 4, weight also 0.1
means that, for any given position in the mask, the upper neighbor has to be at least two passes away (cannot be equal, and cannot be either the preceding or the following value), and the left neighbor should be within a distance of zero, one, three or five (assuming for instance a printmask in a six-pass print mode).
This approach easily allows for constraining a mask such that no solution exists. Therefore care must be taken to ensure that a solution space does exist.
Another, less general but more intuitive way of specifying neighborhood constraints is the constraint matrix. It simply sets a value for each neighbor. That value is the distance, in number of passes, outside which the neighbor is expected to be from the pivotal point. In this example
{00100}
{01110}
{12x11}
{00100}
the xe2x80x9cxxe2x80x9d represents the pivotal point. The two to the left of the x means that the left horizontal neighbor is supposed to be outside an open range of two centered on x. If for example x=4, the left neighbor can be anything except three, four or five. Every point in the mask, when considered the pivot point, should comply with these restrictions.
Neighborhood constraints can be applied within a single plane of a mask, or can be used to relate different planes or different masks between them. As an example, suppose that an eight-pass printmask is to be built for a printer that can print two drops per pixel, but can only print one drop in a given location per pass. The mask must have two planes, and the two numbers corresponding to the same pixel on the two planes must always be different. Additionally, no point should fire in the same pass as the preceding or following pixel. These constraints can be written as follows, and will be explained below.
For the first layer: {1x1}xe2x80x94applied to itself
For the second layer: {1x1}xe2x80x94applied to itself and
The first-layer constraint, and the first constraint in the second-layer set, are the same, xe2x80x9c{1x1}xe2x80x9d. This means that no consecutive neighbors are firing in the same pass.
The following group of constraints for the second layer has three lines. The first line says that, for the position (0,0)xe2x80x94that is, for the same location, but in the other layerxe2x80x94at a distance of zero, or in other words in the same pass, the weight is 0.0, forbidden. Thus two drops cannot be fired into the same pixel-grid location in both passes. The next two lines in the second-layer constraints enforce a requirement that the point in the second plane must also be different from the two horizontal neighbors in the first plane.
The neighborhood constraints have a symmetry redundancy. If the constraint {1x} is imposed for all the points, the converse constraint {x1} will also be fulfilled.
This property will be called polar symmetry. It represents a mathematical generalization that is important to the most-efficient practice of the invention, since it facilitates the progress of mask-building along a simple track from one corner of the mask grid across the first row, and then rasterwise similarly across the next row and so forth.
(2) Pen-usage Constraints
This type of constraint specifies restrictions in the way the nozzles of the pen are used. For building printmasks, the fast mask generation method currently uses two types of nozzle constraint:
Nozzle-usage acceptance defines the level of acceptability of a given nozzle. Acceptability of zero means forbidden, acceptability of one means accepted without restriction. Any number in the closed range [1,0] is allowed.
Nozzle-usage distribution defines an expected or intended distribution of the nozzles. Here a one still means unlimited usage and a zero means forbidden, but the values within the range are specific fractions of use, or duty cycle, desired.
As an example of the difference between these two kinds of constraint, if 0.1 is specified as the usage acceptance of a particular nozzle, that nozzle is acceptable to use but only if there is no better option. If 0.1 is specified as the usage distribution of a particular nozzle, then when printing with the fully created mask this nozzle is expected to be used exactly ten percent of the time it would have been used normallyxe2x80x94i.e. in a conventional system.
Basic Algorithm
The building of a multilayer, sequential mask thus can be reduced to the problem of building each layer of the mask, with some constraints acting between layers. The fundamental algorithm preferably builds a plane by traversing the matrix sequentially, top-down and left-to-right (although other orders can be used without loss of generality).
When any given position of the mask is to be filled, all the existing neighbors (both in the plane being built and in the reference planes) have to be checked following the neighborhood-constraint definitions. The nozzle-usage acceptability and distribution tables, too, have to be checked. This implies, for each pass number, computing the nozzle that will fire it, checking this nozzle in a lookup table, and assigning the weight to the pass number in accordance.
After all the constraints have been applied to all the pass numbers, a set of weights for each possible candidate (pass number) is defined. The next step is to consolidate the different weights assigned to each candidate into one number.
The fast mask generator algorithm does this by assigning a zero (forbidden) for the final weight of a zero is present in any of the values assigned by the constraints, or otherwise a weighted average of all the values. Each value is weighted by the relative importance that the constraint which set it has assigned.
After all the candidates have been assigned a weight, taking into account all the constraints, a candidate has to be chosen to fill the position. The algorithm offers two approaches: the deterministic approach, which consists in choosing the best option (the candidate that has the highest weight), and the randomized approach, which treats the weight of each candidate as a probability.
Using the first option typically yields very ordered masks. The second option gives more random masks, with appearance that is more grainy but less mottled (i.e. repetitive).
Actual implementation of the algorithm allows the user to choose a degree of randomness: a value between zero and one, meaning the fraction of points within the mask that are to be chosen using the randomized strategy. All the rest are assigned deterministically, i.e. by picking the highest weighted candidate. The points that will be set with the randomized strategy are also randomly selected.
In one desirable variant, the degree of randomness is chosen automatically in response to an analysis of xe2x80x9cactivityxe2x80x9d in the image. This form of the invention will be explained more fully below.
The foregoing may convey a general flavor of the subject matter of this document. This discussion now turns to a more formal presentation. In its preferred embodiments, the present invention has several aspects or facets that can be used independently, although they are preferably employed together to optimize their benefits.
In preferred embodiments of a first of its facets or aspects, the invention is a method of preparing and using a mask for incremental printing, using a preestablished program that incorporates complete conditions for a usable mask. The method includes the step of automatically operating the preestablished program that incorporates complete conditions for a usable mask.
This step produces a usable substantially unitary mask in substantially each attempt by the program. The method also includes the step of then automatically using the produced substantially unitary maskxe2x80x94or storing it for later use. The produced mask is for use substantially in common over an entire image, and substantially without human intervention as to mask content.
The term xe2x80x9cunitaryxe2x80x9d, and the reference to use xe2x80x9csubstantially in common over an entire imagexe2x80x9d, for purposes of this document, merely mean that one single mask pattern is used throughout printing of an imagexe2x80x94in other words, that no more than one pattern is used. The mask, however, is not necessarily the size of the full image or a full page. As will be seen shortly, the mask may be either such a full-size mask or a smaller mask that is stepped or xe2x80x9ctiledxe2x80x9d across the image or down the image, or both.
The foregoing may constitute a description or definition of the first facet of the invention in its broadest or most general form. Even in this general form, however, it can be seen that this aspect of the invention significantly mitigates the difficulties left unresolved in the art.
In particular, as will be seen in following sections of this document, the very capability to produce a mask very reliably and systematically is a key to correcting those difficulties. This first aspect of the invention accordingly eliminates the conventional reliance upon masks that are too small to avoid repeating patterns, and masks that are at the same time too large to provide economically within a printer, and masks that must be prepared at the factory and therefore cannot accommodate operating conditions.
Although this aspect of the invention in its broad form thus represents a significant advance in the art, it is preferably practiced in conjunction with certain other features or characteristics that further enhance enjoyment of overall benefits.
For example, it is preferred that the operating step include the substeps of:
considering candidate pass numbers, for a particular position in the mask, and expressing the favorability of each candidate pass number, with regard to each of plural neighboring positions, as a xe2x80x9cneighborhood constraintxe2x80x9d in the form of a respective weight;
consolidating the weights to obtain a single measure of favorability for each candidate pass number;
based on the single measure of favorability, choosing one of the candidate pass numbers for use at the particular position in the mask; and
repeating the considering and expressing step, the consolidating step, and the choosing step for each other position in the mask.
Other preferences include limiting mask production based on relationships among successive layers of colorant; controlling the number of constraints so that adequate degrees of freedom remain to ensure that the program can find a solution in substantially each attempt; automatically selecting a balance between the relative degree of randomness and determinism in a mask to be produced; identifying nearby positions only by a substantially generalized explicit notation that is relative, substantially without reference to absolute position in the mask; and with respect to each nearby position that is thus identified by the generalized notation, expressing in only a substantially generalized explicit notation the acceptability of inking said pixel position in particular inkdrop planes of the mask.
Generalized notation is an important preference in the successful practice of this invention. One preferred type of such notation is use of a first numerical value representing a particular distance in three dimensions within the successive inkdrop planes; and coupled with the first numerical value, a second numerical value representing acceptability of inking at said particular distance. The significance of that second value may be a prohibition of inking, a relative permissibility of inking, or a relative probability to be applied in determining inking.
Another type of generalized notation includes a local grid including a representation of the pixel position of interest and some nearby pixel positions; and in at least some positions within the local grid, relative to the pixel under calculation, a numerical representation of the permissible or preferable distance to a position where inking may occur. It has been found that this type of notation is particularly powerful when the expressing step includes applying a condition that is substantially polar symmetric.
A second aspect of the invention is a method of preparing and using a mask for incremental printing. The method includes the step of, for a particular pixel position in a mask to be prepared, determining a multiplicity of numerical weighting values that respectively represent relative acceptability of inking in a particular inkdrop plane with respect to each of a multiplicity of operating conditions or other nearby positions.
Another step is consolidating the multiplicity of numerical weighting values to determine substantially a single numerical weighting value that represents overall relative acceptability of inking at the particular pixel position in the particular inkdrop plane.
The foregoing may constitute a description or definition of the second facet of the invention in its broadest or most general form. Even in this general form, however, it can be seen that this aspect of the invention too significantly mitigates the difficulties left unresolved in the art.
In particular, the use of weightings in a generalized notation represents an extremely powerful strategy for taking into account a very large number of operating conditions and constraints of various kinds, particularly with respect to inking levels in different inkdrop layers or planes. Thus again this second aspect of the invention serves as a key to resolution of difficult obstacles to a mask-generating system that can function quickly and yet with extreme reliability.
Preferences in regard to this second aspect of the invention will be elaborated further, later in this document. They particularly include evaluating the potential use of certain print nozzles for inking at a particular pixel position in a mask to be prepared; and taking into account the results of the evaluating step in determining relative acceptability of inking that particular pixel position, in a particular inkdrop plane, to prepare the mask.
In a third basic aspect or facet, the invention is a method for generating and employing masks for use in incremental printing, using a self-standing input text file of mask constraints, and also using a mask-generating control algorithm. The program includes the step of automatically reading the self-standing input text file to accept such constraints.
Another step is automatically accepting any definition of a mask-generating modular control algorithm that applies the mask constraints. Still another step is automatically generating a mask, under control of a printmask-generating modular control algorithm.
Further steps include automatically operating the defined mask-generating modular control algorithm to apply the mask constraints and thereby control the mask-generating step; and automatically forwarding the generated mask for use, or for storage and later use, in a printer or a printer driver for operating the printer to print images.
This third aspect of the invention thus focuses upon modularity of the primary algorithm or algorithms, as well as other forms of input. This characteristic renders the invention as a tool still more powerful. A preference in regard to this facet of the invention is combination of the host program with a mask-generating modular control-algorithm definition, functionally interfaced to the accepting step for acceptance thereby.
In a fourth aspect, the invention is a method for generating and employing masks for use in incremental printing, using a self-standing input text file of mask constraints, and also using a mask-optimizing control algorithm. The method includes the step of reading the self-standing input text file to accept such constraints.
It also includes applying the accepted constraints to generate a mask; and accepting any definition of a mask-optimizing modular control algorithm that receives said generated mask as an input and reprocesses said received mask to substantially optimize it for image quality. Other steps are operating the accepted mask-optimizing modular control algorithm to reprocess said received mask to substantially optimize it for image quality; and forwarding the optimized mask for use, or for storage and later use, in a printer or a printer driver for operating the printer to print images.
This aspect is particularly useful in that it provides a program that can correct its own imperfections in first-round mask generation efforts, if more-highly optimized results are desired.
All of the foregoing operational principles and advantages of the present invention will be more fully appreciated upon consideration of the following detailed description, with reference to the appended drawings, of which: